{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Simplified Fractions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: simplifiedFractions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最简分数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于&nbsp;&nbsp;<code>n</code>&nbsp;的 <strong>最简&nbsp;</strong>分数&nbsp;。分数可以以 <strong>任意&nbsp;</strong>顺序返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>[&quot;1/2&quot;]\n",
    "<strong>解释：</strong>&quot;1/2&quot; 是唯一一个分母小于等于 2 的最简分数。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>[&quot;1/2&quot;,&quot;1/3&quot;,&quot;2/3&quot;]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 4\n",
    "<strong>输出：</strong>[&quot;1/2&quot;,&quot;1/3&quot;,&quot;1/4&quot;,&quot;2/3&quot;,&quot;3/4&quot;]\n",
    "<strong>解释：</strong>&quot;2/4&quot; 不是最简分数，因为它可以化简为 &quot;1/2&quot; 。</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [simplified-fractions](https://leetcode.cn/problems/simplified-fractions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [simplified-fractions](https://leetcode.cn/problems/simplified-fractions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '3', '4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(1, i):\n",
    "                if math.gcd(i, j) == 1:\n",
    "                    ans.append(f\"{j}/{i}\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "        for i in range(1, n):\n",
    "            for j in range(i+1, n+1):\n",
    "                if self.gcd(i, j) == 1:\n",
    "                    res.append(f\"{i}/{j}\")\n",
    "        return res\n",
    "\n",
    "                \n",
    "\n",
    "    def gcd(self, a, b):\n",
    "        while b:\n",
    "            a, b = b, a % b\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        \"\"\"\n",
    "        分母的取值范围为 [2, n]， 分子的取值范围为 [1, n - 1]，要求分数最简，所以分子和分母的最大公约数应该为 1，同时遍历分子和分母，即可求得题解\n",
    "        \"\"\"\n",
    "        \n",
    "        return [f\"{numerator}/{denominator}\" for denominator in range(2, n + 1) for numerator in range(1, denominator) if gcd(denominator, numerator) == 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        from fractions import Fraction\n",
    "        op=[]\n",
    "        i=2\n",
    "        while i<=n:\n",
    "            p=1\n",
    "            while p<i:\n",
    "                f = Fraction(p, i)\n",
    "                if f.numerator==p:\n",
    "                    op.append(\"{}/{}\".format(p, i))\n",
    "                p+=1\n",
    "            i+=1\n",
    "        return op\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        def gcd(i, j):\n",
    "            while j:\n",
    "                i, j = j, i % j\n",
    "            return i\n",
    "        \n",
    "        res = []\n",
    "\n",
    "        for i in range(n, 1, -1):\n",
    "            for j in range(i, 0, -1):\n",
    "\n",
    "                if j == 1 or gcd(i, j) == 1:\n",
    "                    res.append(f\"{j}/{i}\")\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        return [f\"{numerator}/{denominator}\" for denominator in range(2, n + 1) for numerator in range(1, denominator) if gcd(denominator, numerator) == 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        res=[]\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,i):\n",
    "              #  print(i,j)\n",
    "                if gcd(i,j)!=1:continue\n",
    "                a=str(j)+\"/\"+str(i)\n",
    "                res.append(a)\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        \"\"\"\n",
    "        分母的取值范围为 [2, n]， 分子的取值范围为 [1, 分母]，要求分数最简，所以分子和分母的最大公约数应该为 1，同时遍历分子和分母，即可求得题解\n",
    "        \"\"\"\n",
    "\n",
    "        result = []\n",
    "\n",
    "        # 遍历分母\n",
    "        for denominator in range(2, n + 1):\n",
    "\n",
    "            # 遍历分子\n",
    "            for numerator in range(1, denominator):\n",
    "                \n",
    "                # 分子分母的最大公约数为 1，说明是最简分数\n",
    "                if gcd(denominator, numerator) == 1:\n",
    "                    \n",
    "                    # 加入结果集\n",
    "                    result.append(f\"{numerator}/{denominator}\")\n",
    "\n",
    "        return result\n",
    "\n",
    "        # return [f\"{numerator}/{denominator}\" for denominator in range(2, n + 1) for numerator in range(1, denominator) if gcd(denominator, numerator) == 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "\n",
    "        for a in range(2, n + 1):\n",
    "            for b in range(1, a):\n",
    "                if gcd(a, b) == 1:\n",
    "                    res.append(f'{b}/{a}')\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "        for den in range(2, n + 1): \n",
    "            for num in range(1, den):\n",
    "                if gcd(den, num) == 1:\n",
    "                    ans.append(\"%d/%d\" % (num, den))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(1,i):\n",
    "                if math.gcd(i,j)==1:\n",
    "                    res.append(\"{}/{}\".format(j,i))\n",
    "        return res\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        s = set()\n",
    "        for i in range(1, n):\n",
    "            for j in range(i + 1, n+1):\n",
    "                k = gcd(i, j)\n",
    "                s.add(str(i // k) + \"/\" + str(j // k))\n",
    "        return list(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        import math\n",
    "        ans = []\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,i):\n",
    "                if math.gcd(i,j) == 1:\n",
    "                    ans.append(str(j)+'/'+str(i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        return [f\"{numerator}/{denominator}\" for denominator in range(2, n + 1) for numerator in range(1, denominator) if gcd(denominator, numerator) == 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        return [f\"{i}/{j}\" for i in range(1, n+1) for j in range(i, n+1) if ((i != j) and math.gcd(i,j) == 1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(1, i):\n",
    "                if gcd(i, j) == 1:\n",
    "                    ans.append(str(j) + \"/\" + str(i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        return [f'{j}/{i}' for i in range(2, n + 1) for j in range(1, i) if gcd(i, j) == 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(a,b):\n",
    "    k = math.gcd(a,b)\n",
    "    if k != 1:\n",
    "        return a//k,b//k\n",
    "    return a,b\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        res = set()\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(1, i):\n",
    "                a, b = func1(j,i)\n",
    "                res.add(str(a)+'/'+str(b))\n",
    "        return list(res)                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        if n == 1:\n",
    "            return []\n",
    "        ans = []\n",
    "        for i in range(1,n):\n",
    "            for j in range(i+1,n+1):\n",
    "                if gcd(i,j) == 1:\n",
    "                    ans.append(str(i)+'/'+str(j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def gcd(a, b):\n",
    "    if b == 0:\n",
    "        return a\n",
    "    return gcd(b, a % b)\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(1, i):\n",
    "                if gcd(i,j) == 1:\n",
    "                    res.append(f'{j}/{i}')\n",
    "        return res                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from math import gcd\n",
    "class Solution:\n",
    "    # @ lambda _ : print(_(_, n))\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        if n == 1 : return []\n",
    "        Num = [x for x in range(1, n + 1)]\n",
    "        ans = []\n",
    "        for i in range(len(Num)):\n",
    "            for x in range(i + 1, len(Num)):\n",
    "                if i == len(Num) - 1:\n",
    "                    break\n",
    "                if gcd(Num[i], Num[x]) == 1:\n",
    "                    ans.append(str(Num[i]) + '/' + str(Num[x]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(1,i):\n",
    "                if gcd(i,j) == 1:\n",
    "                    res.append(str(j)+'/'+str(i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        if n == 1:\n",
    "            return []\n",
    "        if n == 2:\n",
    "            return [\"1/2\"]\n",
    "        res = []\n",
    "        for i in range(1, n):\n",
    "            if math.gcd(i, n) == 1:\n",
    "                res.append(\"{}/{}\".format(i, n))\n",
    "        return self.simplifiedFractions(n-1) + res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(1, i):\n",
    "                if gcd(i, j) == 1:\n",
    "                    ans.append(str(j) + \"/\" + str(i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        return [f\"{numerator}/{denominator}\" for denominator in range(2, n + 1) for numerator in range(1, denominator) if gcd(denominator, numerator) == 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        def are_colprime(a,b):\n",
    "            while b != 0:\n",
    "                a,b = b, a % b\n",
    "            return a == 1\n",
    "        ans = []\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if i == 1 and i < j:\n",
    "                    ans.append(str(i) + '/' + str(j))\n",
    "                elif i < j and are_colprime(j,i):\n",
    "                    ans.append(str(i) + '/' + str(j))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        def gcd(num1, num2):\n",
    "            if(num1 < num2):\n",
    "                num1, num2 = num2, num1\n",
    "            if(num1 % num2 == 0):\n",
    "                return num2\n",
    "            return gcd(num2, num1 % num2)\n",
    "        result = set()\n",
    "        for d in range(2,n+1):\n",
    "            for m in range(1,d):\n",
    "                g = gcd(d, m)\n",
    "                result.add(str(m//g) + '/' + str(d//g))\n",
    "        return list(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        return [f\"{numerator}/{denominator}\" for denominator in range(2, n + 1) for numerator in range(1, denominator) if gcd(denominator, numerator) == 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        def gcd(num1, num2):\n",
    "            if(num1 < num2):\n",
    "                num1, num2 = num2, num1\n",
    "            if(num1 % num2 == 0):\n",
    "                return num2\n",
    "            return gcd(num2, num1 % num2)\n",
    "        result = set()\n",
    "        for d in range(2,n+1):\n",
    "            for m in range(1,d):\n",
    "                g = gcd(d, m)\n",
    "                s = str(m//g) + '/' + str(d//g)\n",
    "                result.add(s)\n",
    "        return list(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        def gcd(l,r):return gcd(r%l,l) if r%l else l\n",
    "        return [f'{i}/{j}' for i in range(1,n) for j in range(i+1,n+1) if 1 in [i,gcd(i,j)]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        ans=[]\n",
    "        def gcd(x,y):\n",
    "            if y==0:\n",
    "                return x\n",
    "            x,y=max(x,y),min(x,y)\n",
    "            return gcd(y,x%y)\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(1,i):\n",
    "                if gcd(i,j)==1:\n",
    "                    ans.append(str(j)+'/'+str(i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "        for i in range(2, n+1):\n",
    "            res.append('1'+'/'+str(i))\n",
    "            for j in range(2, i):\n",
    "                first, second = i, j\n",
    "                flag = False\n",
    "                while abs(first-second) >= 2:\n",
    "                    if max(first, second)%min(first, second) == 0:\n",
    "                        flag = True\n",
    "                        break\n",
    "                    first, second = min(first, second), abs(first-second)\n",
    "                if not flag:\n",
    "                    res.append(str(j)+'/'+str(i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        return [f\"{j}/{i}\" for i in range(2, n + 1) for j in range(1, i) if gcd(i, j) == 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        def isJian(n1, n2):\n",
    "            tmp = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53]\n",
    "            if n1 == 1:\n",
    "                return True\n",
    "            for i in tmp:\n",
    "                if n1 % i == 0 and n2 % i == 0:\n",
    "                    return False\n",
    "            return True\n",
    "            \n",
    "        if n == 1:\n",
    "            return []\n",
    "        if n == 2:\n",
    "            return ['1/2']\n",
    "        if n >= 3:\n",
    "            ans = self.simplifiedFractions(n-1)\n",
    "            for i in range(1,n):\n",
    "                if isJian(i, n):\n",
    "                    ans.append(str(i)+'/'+str(n))\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        def gcd(a: int, b: int) -> int:\n",
    "            if a < b:\n",
    "                return gcd(b, a)\n",
    "            while a % b != 0:\n",
    "                a, b = b, a%b\n",
    "            return b\n",
    "\n",
    "        ans = []\n",
    "        for i in range(n+1):\n",
    "            for j in range(1, i):\n",
    "                if gcd(i, j) == 1:\n",
    "                    ans.append(f\"{j}/{i}\")\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def gcd(a, b):\n",
    "    if b == 0:\n",
    "        return a\n",
    "    return gcd(b, a % b)\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(1, i):\n",
    "                if gcd(i,j) == 1:\n",
    "                    res.append(f'{j}/{i}')\n",
    "        return res                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        def gcd(a, b):\n",
    "            return a if b == 0 else gcd(b, a%b)\n",
    "        ans = []\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,i):\n",
    "                if gcd(i,j) == 1:\n",
    "                    ans.append(str(j)+'/'+str(i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        \n",
    "        def gcd(m,n):\n",
    "            if n > m: return gcd(n, m)\n",
    "            if m % n == 0: return n\n",
    "            return gcd(n, m%n)\n",
    "\n",
    "        ans = set()\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(1, i):\n",
    "                x = gcd(i, j)\n",
    "                ans.add(str(j//x) + '/' + str(i//x))\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        def gcd(a, b):\n",
    "            while b:\n",
    "                temp = a % b\n",
    "                a, b = b, temp\n",
    "            return a\n",
    "        ans = []\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(1, i):\n",
    "                if gcd(i, j) == 1:\n",
    "                    ans.append(str(j)+\"/\"+str(i))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "        for b in range(2, n + 1):\n",
    "            for a in range(1, b):\n",
    "                if gcd(a, b) == 1:\n",
    "                    ans.append(str(a) + '/' + str(b))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        res=[]\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(1,i):\n",
    "                if gcd(i,j)==1:\n",
    "                    res.append(str(j)+\"/\"+str(i))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(1, i):\n",
    "                if gcd(i,j) == 1:\n",
    "                    res.append(f'{j}/{i}')\n",
    "        return res                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from math import gcd\n",
    "class Solution:\n",
    "    # @ lambda _ : print(_(_, n))\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        if n == 1 : return []\n",
    "        Num = [x for x in range(1, n + 1)]\n",
    "        ans = []\n",
    "\n",
    "        for i in range(len(Num)):\n",
    "            for x in range(i + 1, len(Num)):\n",
    "                ans.append(str(Num[i]) + '/' + str(Num[x])) if gcd(Num[i], Num[x]) == 1 else ...\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcd(self,a,b):\n",
    "        if not b:\n",
    "            return a\n",
    "        return self.gcd(b,a%b)\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        fenmu = [i for i in range(2,n+1)]\n",
    "        res = []\n",
    "        for i in fenmu:\n",
    "            for j in range(1,i):\n",
    "                if self.gcd(j,i) != 1:\n",
    "                    continue\n",
    "                res.append(f'{str(j)}/{str(i)}')\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "        for deno in range(2, n+1):\n",
    "            for i in range(deno):\n",
    "                if gcd(i, deno) == 1:\n",
    "                    ans.append(f'{i}/{deno}')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        return [f\"{numerator}/{denominator}\" for denominator in range(2, n + 1) for numerator in range(1, denominator) if gcd(denominator, numerator) == 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        fhsz = [f\"1/{i}\" for i in range(2, n+1)]\n",
    "        for i in range(2, n):\n",
    "            fm = [j for j in range(2, i+1) if i%j == 0]\n",
    "            for j in range(i+1, n+1):\n",
    "                if all(j%z for z in fm):\n",
    "                    fhsz.append(f\"{i}/{j}\")\n",
    "        return fhsz\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from math import gcd\n",
    "class Solution:\n",
    "    # @ lambda _ : print(_(_, n))\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        if n == 1 : return []\n",
    "        Num = [x for x in range(1, n + 1)]\n",
    "        ans = []\n",
    "\n",
    "        for i in range(len(Num)):\n",
    "            for x in range(i + 1, len(Num)):\n",
    "                ans.append(str(Num[i]) + '/' + str(Num[x])) if gcd(Num[i], Num[x]) == 1 else ...\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        def gcd(a, b):\n",
    "            return gcd(b, a % b) if b != 0 else a\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                if gcd(i, j) == 1:\n",
    "                    res.append(\"{}/{}\".format(i, j))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        def gcd(a: int, b: int) -> int:\n",
    "            if a < b:\n",
    "                return gcd(b, a)\n",
    "            while b != 0:\n",
    "                a, b = b, a%b\n",
    "            return a\n",
    "\n",
    "        ans = []\n",
    "        for i in range(n+1):\n",
    "            for j in range(1, i):\n",
    "                if gcd(i, j) == 1:\n",
    "                    ans.append(f\"{j}/{i}\")\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        val = []\n",
    "        fenshu = []\n",
    "        for i in range(1,n):\n",
    "            for j in range(2,n+1):\n",
    "                if i < j:\n",
    "                    val.append(i/j)\n",
    "                    if val.count(i/j) == 1:\n",
    "                        fenshu.append(str(i) + '/' + str(j))\n",
    "        return fenshu\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        ans=[]\n",
    "        if n==1:\n",
    "            return []\n",
    "        def check(x):\n",
    "            tot=x\n",
    "            vis=[False for i in range (x)]\n",
    "            p=2\n",
    "            while x>=p:\n",
    "                if x%p==0:\n",
    "                    while x%p==0:\n",
    "                        x=x//p\n",
    "                    for i in range(p,tot,p):\n",
    "                        vis[i]=True\n",
    "                p+=1\n",
    "            for i in range(1,tot):\n",
    "                if not vis[i]:\n",
    "                    ans.append(str(i)+'/'+str(tot))\n",
    "\n",
    "        for i in range(2,n+1):\n",
    "            check(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def simplifiedFractions(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        result=[]\n",
    "        num_result=[]\n",
    "        if n<2:\n",
    "            return result\n",
    "        for down in range(2,n+1):\n",
    "            for up in range(1,down):\n",
    "                if up!=1 and up/down in num_result:\n",
    "                    continue\n",
    "                else:\n",
    "                    result.append(str(up)+'/'+str(down))\n",
    "                    num_result.append(up/down)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        val = []\n",
    "        fenshu = []\n",
    "        for j in range(2,n+1):\n",
    "            for i in range(1,j):\n",
    "                    val.append(i/j)\n",
    "                    if val.count(i/j) == 1:\n",
    "                        fenshu.append(str(i) + '/' + str(j))\n",
    "        return fenshu\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, x: int) -> List[str]:\n",
    "        ans = []\n",
    "        d = set()\n",
    "        for n in range(2, x+1):\n",
    "            for i in range(1, n):\n",
    "                if (i / n) not in d:\n",
    "                    d.add(i/n)\n",
    "                    ans.append(str(i) + '/' + str(n))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simplifiedFractions(self, n: int) -> List[str]:\n",
    "        already = set()\n",
    "        res = []\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, i):\n",
    "                tmp = j / i\n",
    "                if tmp not in already:\n",
    "                    already.add(tmp)\n",
    "                    res.append(\"%d/%d\"%(j,i))\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
